﻿#include <stdio.h>
#include <stdlib.h>


struct node {
	int data;
	node* next;
};
node* insert(node* head, node* p)
{
	node* p1, * p2;
	if (head == NULL) {
		head = p;
		p->next = NULL;
		return head;
	}
	if (head->data >= p->data) {
		p->next = head;
		head = p;
		return head;
	}
	p1 = head;
	p2 = head;
	while (p2->next && p2->data < p->data) {
		p1 = p2;
		p2 = p2->next;
	}
	if (p2->data < p->data) {
		p2->next = p;
		p->next = NULL;
	}
	else {
		p->next = p2;
		p1->next = p;
	}
	return head;
}

node* create_sort(void)
{
	node* p1, * head = 0;
	int a;
	printf("建立一条有序链表，请输入数据，以-1结束：");
	scanf_s("%d", &a);
	while (a != -1)
	{
		p1 = (node*)malloc(sizeof(node));
		p1->data = a;
		head = insert(head, p1);
		scanf_s("%d", &a);
	}
	return (head);
}
//输出链表上各个节点的值 111
void print(const node* head)
{
	const node* p;
	p = head;
	printf("链表上各个节点的数据为：\n");
	while (p != NULL) {
		printf(" %d\t", p->data);
		p = p->next;
	}
	printf("\n");
}
//删除链表上具有指定值的一个节点
node* delete_one_node(node* head, int num)
{
	node* pl, * p2;
	if (head == NULL) {
		printf("链表为空，无节点可删!\n");
		return(NULL);
	}
	if (head->data == num) {
		pl = head;
		head = head->next;
		free(pl);
		printf("删除了一个节点!\n");
	}
	else {
		p2 = pl = head;
		while (p2->data != num && p2->next != NULL) {
			pl = p2;
			p2 = p2->next;
		}
		if (p2->data == num) {
			pl->next = p2->next;
			free(p2);
			printf("删除了一个节点!\n");
		}
		else printf("%d链表上没找到要删除的节点!\n", num);
	}
	return (head);
}
//释放链表的节点空间
void deleteetechain(node* h)
{
	node* p1;
	while (h) {
		p1 = h;
		h = h->next;
		free(p1);
	}
	printf("已释放链表的节点空间!\n");
}
int count(node* head)//求链表的节点数
{
	int n;
	node* p;
	p = head;
	n = 0;
	while (p != NULL)
	{
		n = n + 1;
		p = p->next;
	}
	return(n);
}
//删除链表上第k个节点
node* find(node* head, int k)
{
	node* p;
	p = head;
	int i;
	for (i = 0; i < k - 1; i++) {
		p = p->next;
	}
	return p;
}
node* delete_k_node(node* head, int k)
{
	int j = 1;
	node* p, * pl;
	if (head == NULL) {
		printf("链表为空，无节点可删!\n");
		return (NULL);
	}
	p = head;
	if (k == 1) {
		p = head;
		head = head->next;
		free(p);
		printf("删除了第一个节点!\n");
	}
	else {
		p = find(head, k - 1);//查找第k-1个节点，并由p指向该节点111
		if (p->next != NULL)
		{
			pl = p->next;
			p->next = pl->next;
			free(pl);
			printf("删除了第%d个背点!\n", k);
		}
		return (head);
	}
}

void main(void)
{
	node* head, * p;
	int num;
	int k;
	head = create_sort();
	print(head);
	printf("节点数:% d\n", count(head));
	printf("输人要删除节点上的序号!\n");
	scanf_s("%d", &num);
	head = delete_k_node(head, num);
	print(head);
	printf("输入要删除节点上的整数!\n");
	scanf_s("%d", &num);
	head = delete_one_node(head, num);
	print(head);
	printf("输人要插人的整数!\n");
	scanf_s("%d", &num);
	p = (node*)malloc(sizeof(node));
	p->data = num;
	p->next = 0;
	head = insert(head, p);
	print(head);
	deleteetechain(head);
}